
function Node(data, left, right) {
    this.data = data;
    this.count = 1;
    this.left = left;
    this.right = right;
}
Node.prototype.show = function() {
    return this.data;
}

function BST() {
    this.root = null;
}
BST.prototype.insert = function(data) {
    var n = new Node(data, null, null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(true) {
            parent = current;
            if(data < current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
var InOrder = function(node) {
    if(!(node == null)) {
        InOrder(node.left);
        console.log(node.show());
        InOrder(node.right);
    }
}

var PreOrder = function(node) {
    if(!(node == null)) {
        console.log(node.show());
        PreOrder(node.left);
        PreOrder(node.right);
    }
}

var PostOrder = function(node) {
    if(!(node == null)) {
        PostOrder(node.left);
        PostOrder(node.right);
        console.log(node.show());
    }
}

var getMin = function(node) {
    var current = node;
    while(!(current.left == null)) {
        current = current.left
    }
    return current.data;
}

var getSmallest = function(node) {
    var current = node;
    while(!(current.left == null)) {
        current = current.left
    }
    return current;
}

var getMax = function(node) {
    var current = node;
    while(!(current.right == null)) {
        current = current.right
    }
    return current.data;
}
BST.prototype.find = function(data) {
    var current = this.root;
    while(current != null) {
        console.log('current is:', current);
        if(current.data == data) {
            return current;
        }
        if(current.data > data) {
            current = current.left;
            continue;
        }
        if(current.data < data) {
            current = current.right;
            continue;
        }
    }
    return current;
}

function removeNode(node, data) {
    if(node == null) {
        return null;
    }
    if(data == node.data) {
        if(node.left == null && node.right == null) {
            return null;
        }
        if(node.left == null) {
            return node.right;
        }
        if(node.right == null) {
            return node.left;
        }
        var tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.left, tempNode.data);
        return node;
    } else if(data < node.data) {
        console.log("node.data:", node.data);
        node.left = removeNode(node.left, data);
        console.log("node.left:", node.left);
        return node; 
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
}

BST.prototype.update = function(data) {
    var grade = this.find(data);
    grade.count++;
    return grade;
}

var bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(1);
bst.insert(2);

bst.insert(8);

bst.insert(7);
bst.insert(4);
bst.insert(6);
bst.insert(10);
bst.insert(9);
removeNode(bst.root, 1);